package 数据结构设计高频题;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 实现LRU结构
// 测试链接 : https://leetcode.cn/problems/lru-cache/
class LRUCache {

    class DoubleNode {
        int key;
        int val;
        DoubleNode next;
        DoubleNode last;

        public DoubleNode(int key, int val) {
            this.key = key;
            this.val = val;
            this.next = null;
            this.last = null;
        }
    }

    class DoubleList{
        private DoubleNode head;
        private DoubleNode tail;

        public DoubleList() {
            this.head = null;
            this.tail = null;
        }

        public void addNode(DoubleNode newNode){
            if(newNode == null){
                return;
            }
            if(head == null){
                head = newNode;
                tail = newNode;
            }else {
                tail.next = newNode;
                newNode.last = tail;
                tail = newNode;
            }
        }

        public void moveNodeToTail(DoubleNode node){
            if(node == tail){
                return;
            }else if(node == head){
                head = node.next;
                head.last = null;
            }else {
                node.last.next = node.next;
                node.next.last = node.last;
            }
            tail.next = node;
            node.last = tail;
            node.next = null;
            tail = node;
        }

        public DoubleNode removeHead(){
            if (head == null){
                return  null;
            }
            DoubleNode ans = head;
            if(head == tail){
                head = null;
                tail = null;
            }else {
                head = ans.next;
                ans.next = null;
                head.last = null;
            }
            return ans;
        }
    }

    private Map<Integer, DoubleNode> keyNodeMap;
    private DoubleList nodeList;
    private int capacity;
    public LRUCache(int capacity) {
        keyNodeMap = new HashMap<>();
        nodeList = new DoubleList();
        this.capacity = capacity;
    }

    public int get(int key) {
        if(keyNodeMap.containsKey(key)){
            DoubleNode node = keyNodeMap.get(key);
            nodeList.moveNodeToTail(node);
            return node.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        if(keyNodeMap.containsKey(key)){
            DoubleNode node = keyNodeMap.get(key);
            node.val = value;
            nodeList.moveNodeToTail(node);
        }else {
            if(keyNodeMap.size() == capacity){
                DoubleNode head = nodeList.removeHead();
                keyNodeMap.remove(head.key);
            }
            DoubleNode newNode = new DoubleNode(key, value);
            nodeList.addNode(newNode);
            keyNodeMap.put(key, newNode);
        }
    }
}
